
<!DOCTYPE html>
<!--[if IEMobile 7 ]><html class="no-js iem7"><![endif]-->
<!--[if lt IE 9]><html class="no-js lte-ie8"><![endif]-->
<!--[if (gt IE 8)|(gt IEMobile 7)|!(IEMobile)|!(IE)]><!--><html class="no-js" lang="en"><!--<![endif]-->
<head>
  <meta charset="utf-8">
  <title>Yebangyu's Blog</title>
  <meta name="author" content="Yebangyu">

  
  <meta name="description" content="记录2017年阅读过的技术相关的书籍、博客、Slides等 Machine Learning Deep Learning, By Ian Goodfellow et al An overview of gradient descent optimization algorithms &hellip;">
  

  <!-- http://t.co/dKP3o1e -->
  <meta name="HandheldFriendly" content="True">
  <meta name="MobileOptimized" content="320">
  <meta name="viewport" content="width=device-width, initial-scale=1">

  
  <link rel="canonical" href="http://www.yebangyu.org/">
  <link href="/favicon.png" rel="icon">
  <link href="/stylesheets/screen.css" media="screen, projection" rel="stylesheet" type="text/css">
  <link href="/atom.xml" rel="alternate" title="Yebangyu's Blog" type="application/atom+xml">
  <script src="/javascripts/modernizr-2.0.js"></script>
  <script src="//ajax.lug.ustc.edu.cn/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
  <script>!window.jQuery && document.write(unescape('%3Cscript src="/javascripts/libs/jquery.min.js"%3E%3C/script%3E'))</script>
  <script src="/javascripts/octopress.js" type="text/javascript"></script>
  <!--Fonts from Google"s Web font directory at http://google.com/webfonts -->
<link href="//fonts.lug.ustc.edu.cn/css?family=PT+Serif:regular,italic,bold,bolditalic" rel="stylesheet" type="text/css">
<link href="//fonts.lug.ustc.edu.cn/css?family=PT+Sans:regular,italic,bold,bolditalic" rel="stylesheet" type="text/css">
<!-- mathjax config similar to math.stackexchange -->
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
  jax: ["input/TeX", "output/HTML-CSS"],
  tex2jax: {
    inlineMath: [ ['$', '$'] ],
    displayMath: [ ['$$', '$$']],
    processEscapes: true,
    skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
  },
  messageStyle: "none",
  "HTML-CSS": { preferredFont: "TeX", availableFonts: ["STIX","TeX"] }
});
</script>
<script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML" type="text/javascript"></script>

  

</head>

<body   >
  <header role="banner"><hgroup>
  <h1><a href="/">Yebangyu's Blog</a></h1>
  
    <h2>Fond of Concurrency Programming and Machine Learning</h2>
  
</hgroup>

</header>
  <nav role="navigation"><ul class="subscription" data-subscription="rss">
  <li><a href="/atom.xml" rel="subscribe-rss" title="subscribe via RSS">RSS</a></li>
  
</ul>
  
<form action="https://www.google.com/search" method="get">
  <fieldset role="search">
    <input type="hidden" name="sitesearch" value="www.yebangyu.org">
    <input class="search" type="text" name="q" results="0" placeholder="Search"/>
  </fieldset>
</form>
  
<ul class="main-navigation">
  <li><a href="/">Blog</a></li>
  <li><a href="/blog/archives">Archives</a></li>
  <li><a href="/about">About Me</a></li>
</ul>

</nav>
  <div id="main">
    <div id="content">
      <div class="blog-index">
  
  
  
    <article>
      
  <header>
    
      <h1 class="entry-title"><a href="/blog/2017/03/11/2017/">2017技术成长之路</a></h1>
    
    
      <p class="meta">
        




<time class='entry-date' datetime='2017-03-11T15:23:02+08:00'><span class='date'><span class='date-month'>Mar</span> <span class='date-day'>11</span><span class='date-suffix'>th</span>, <span class='date-year'>2017</span></span> <span class='time'>3:23 pm</span></time>
        
      </p>
    
  </header>


  <div class="entry-content"><p>记录2017年阅读过的技术相关的书籍、博客、Slides等</p>

<h2 id="machine-learning">Machine Learning</h2>

<p><a href="https://www.amazon.com/Deep-Learning-Adaptive-Computation-Machine/dp/0262035618/ref=sr_1_1?ie=UTF8&amp;qid=1489217130&amp;sr=8-1&amp;keywords=deep+learning">Deep Learning, By  Ian Goodfellow et al</a></p>

<p><a href="http://sebastianruder.com/optimizing-gradient-descent/">An overview of gradient descent optimization algorithms</a></p>

<p><a href="http://www.di.ens.fr/~fbach/fbach_tutorial_vr_nips_2016.pdf">Stochastic optimization: Beyond stochastic gradients and convexity. Part I</a></p>

<p><a href="http://www.di.ens.fr/~fbach/ssra_tutorial_vr_nips_2016.pdf">Stochastic optimization: Beyond stochastic gradients and convexity. Part II</a></p>

<p><a href="http://engineering.skymind.io/distributed-deep-learning-part-1-an-introduction-to-distributed-training-of-neural-networks">Distributed Deep Learning, Part 1: An Introduction to Distributed Training of Neural Networks</a></p>

</div>
  
  
    <footer>
      <a rel="full-article" href="/blog/2017/03/11/2017/">阅读更多 →</a>
    </footer>
  


    </article>
  
  
    <article>
      
  <header>
    
      <h1 class="entry-title"><a href="/blog/2017/02/17/virtualfunctionandvariadicparametertemplate/">虚函数和变长参数模板的妙用</a></h1>
    
    
      <p class="meta">
        




<time class='entry-date' datetime='2017-02-17T22:32:08+08:00'><span class='date'><span class='date-month'>Feb</span> <span class='date-day'>17</span><span class='date-suffix'>th</span>, <span class='date-year'>2017</span></span> <span class='time'>10:32 pm</span></time>
        
      </p>
    
  </header>


  <div class="entry-content"><p>假如我们需要设计和实现自己的容器，比如说vector，list，queue等。</p>

<p>同一类容器，我们可能有不同的实现和用途，因此我们抽象出了一个Base Class，比如说(以Vector为例)：</p>

<div class="bogus-wrapper"><notextile><figure class="code"><figcaption><span></span></figcaption><div class="highlight"><table><tr><td class="gutter"><pre class="line-numbers"><span class="line-number">1</span>
<span class="line-number">2</span>
<span class="line-number">3</span>
<span class="line-number">4</span>
<span class="line-number">5</span>
<span class="line-number">6</span>
<span class="line-number">7</span>
<span class="line-number">8</span>
<span class="line-number">9</span>
<span class="line-number">10</span>
<span class="line-number">11</span>
<span class="line-number">12</span>
<span class="line-number">13</span>
<span class="line-number">14</span>
<span class="line-number">15</span>
<span class="line-number">16</span>
<span class="line-number">17</span>
<span class="line-number">18</span>
<span class="line-number">19</span>
<span class="line-number">20</span>
<span class="line-number">21</span>
<span class="line-number">22</span>
<span class="line-number">23</span>
<span class="line-number">24</span>
<span class="line-number">25</span>
<span class="line-number">26</span>
<span class="line-number">27</span>
<span class="line-number">28</span>
<span class="line-number">29</span>
<span class="line-number">30</span>
<span class="line-number">31</span>
<span class="line-number">32</span>
<span class="line-number">33</span>
<span class="line-number">34</span>
</pre></td><td class="code"><pre><code class="c++"><span class="line"><span class="cp">#include&lt;iostream&gt;</span>
</span><span class="line"><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span>
</span><span class="line"><span class="k">template</span><span class="o">&lt;</span><span class="k">typename</span> <span class="n">T</span><span class="o">&gt;</span>
</span><span class="line"><span class="k">class</span> <span class="nc">BaseVector</span>
</span><span class="line"><span class="p">{</span>
</span><span class="line"><span class="k">public</span><span class="o">:</span>
</span><span class="line">  <span class="k">virtual</span> <span class="kt">void</span> <span class="n">pre_allocate</span><span class="p">(</span><span class="kt">int</span> <span class="n">capacity</span><span class="p">)</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
</span><span class="line"><span class="p">};</span>
</span><span class="line">
</span><span class="line"><span class="k">template</span><span class="o">&lt;</span><span class="k">typename</span> <span class="n">T</span><span class="o">&gt;</span>
</span><span class="line"><span class="k">class</span> <span class="nc">SmallVector</span><span class="o">:</span> <span class="k">public</span> <span class="n">BaseVector</span><span class="o">&lt;</span><span class="n">T</span><span class="o">&gt;</span> <span class="c1">//一种特定的实现</span>
</span><span class="line"><span class="p">{</span>
</span><span class="line"><span class="k">public</span><span class="o">:</span>
</span><span class="line">  <span class="k">virtual</span> <span class="kt">void</span> <span class="n">pre_allocate</span><span class="p">(</span><span class="kt">int</span> <span class="n">capacity</span><span class="p">)</span>
</span><span class="line">  <span class="p">{</span>
</span><span class="line">    <span class="n">p_</span> <span class="o">=</span> <span class="p">(</span><span class="n">T</span><span class="o">*</span><span class="p">)</span><span class="n">malloc</span><span class="p">(</span><span class="k">sizeof</span><span class="p">(</span><span class="n">T</span><span class="p">)</span> <span class="o">*</span> <span class="n">capacity</span><span class="p">);</span> <span class="c1">//实际里可能不是malloc，而是自己实现的allocator</span>
</span><span class="line">   <span class="c1">//错误处理等等不在本文考虑范围之内</span>
</span><span class="line">    <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">capacity</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span> <span class="p">{</span>
</span><span class="line">      <span class="k">new</span><span class="p">(</span><span class="o">&amp;</span><span class="n">p_</span><span class="p">[</span><span class="n">i</span><span class="p">])</span> <span class="n">T</span><span class="p">();</span> <span class="c1">//预先构造好。注意，这里需要参数个数为0的默认构造函数</span>
</span><span class="line">    <span class="p">}</span>
</span><span class="line">  <span class="p">}</span>
</span><span class="line"><span class="k">private</span><span class="o">:</span>
</span><span class="line">  <span class="n">T</span> <span class="o">*</span><span class="n">p_</span><span class="p">;</span>
</span><span class="line"><span class="p">};</span>
</span><span class="line"><span class="k">class</span> <span class="nc">NoParameters</span>
</span><span class="line"><span class="p">{</span>
</span><span class="line">  <span class="c1">//do something</span>
</span><span class="line"><span class="p">};</span>
</span><span class="line"><span class="kt">int</span> <span class="nf">main</span><span class="p">()</span>
</span><span class="line"><span class="p">{</span>
</span><span class="line">  <span class="n">SmallVector</span><span class="o">&lt;</span><span class="n">NoParameters</span><span class="o">&gt;</span> <span class="n">vec0</span><span class="p">;</span>
</span><span class="line">  <span class="n">vec0</span><span class="p">.</span><span class="n">pre_allocate</span><span class="p">(</span><span class="mi">1000</span><span class="p">);</span>
</span><span class="line">  <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
</span><span class="line"><span class="p">}</span>
</span></code></pre></td></tr></table></div></figure></notextile></div>

<p>没问题。一切完美。不过你试图这样使用vector类，就不行了：</p>

</div>
  
  
    <footer>
      <a rel="full-article" href="/blog/2017/02/17/virtualfunctionandvariadicparametertemplate/">阅读更多 →</a>
    </footer>
  


    </article>
  
  
    <article>
      
  <header>
    
      <h1 class="entry-title"><a href="/blog/2016/12/25/singleton/">Singleton与多线程</a></h1>
    
    
      <p class="meta">
        




<time class='entry-date' datetime='2016-12-25T18:42:32+08:00'><span class='date'><span class='date-month'>Dec</span> <span class='date-day'>25</span><span class='date-suffix'>th</span>, <span class='date-year'>2016</span></span> <span class='time'>6:42 pm</span></time>
        
      </p>
    
  </header>


  <div class="entry-content"><p>如果您和我一样，都只有C++背景，之前对设计模式也一窍不通，那么也没有关系，因为本文不需要您对设计模式有多么了解。</p>

<h2 id="singleton">Singleton模式</h2>

<p>所谓的单例模式，single instance模式，简单实现如下：</p>

<div class="bogus-wrapper"><notextile><figure class="code"><figcaption><span></span></figcaption><div class="highlight"><table><tr><td class="gutter"><pre class="line-numbers"><span class="line-number">1</span>
<span class="line-number">2</span>
<span class="line-number">3</span>
<span class="line-number">4</span>
<span class="line-number">5</span>
<span class="line-number">6</span>
<span class="line-number">7</span>
<span class="line-number">8</span>
<span class="line-number">9</span>
<span class="line-number">10</span>
<span class="line-number">11</span>
<span class="line-number">12</span>
<span class="line-number">13</span>
<span class="line-number">14</span>
<span class="line-number">15</span>
<span class="line-number">16</span>
<span class="line-number">17</span>
</pre></td><td class="code"><pre><code class="c++"><span class="line"><span class="k">class</span> <span class="nc">Singleton</span>
</span><span class="line"><span class="p">{</span>
</span><span class="line">  <span class="k">public</span><span class="o">:</span>
</span><span class="line">    <span class="k">static</span> <span class="n">Singleton</span><span class="o">*</span> <span class="n">instance</span><span class="p">();</span>
</span><span class="line">  <span class="k">private</span><span class="o">:</span>
</span><span class="line">    <span class="k">static</span> <span class="n">Singleton</span><span class="o">*</span> <span class="n">pInstance</span><span class="p">;</span>
</span><span class="line"><span class="p">};</span>
</span><span class="line">
</span><span class="line"><span class="n">Singleton</span><span class="o">*</span> <span class="n">Singleton</span><span class="o">::</span><span class="n">pInstance</span> <span class="o">=</span> <span class="nb">NULL</span><span class="p">;</span>
</span><span class="line">
</span><span class="line"><span class="n">Singleton</span><span class="o">*</span> <span class="n">Singleton</span><span class="o">::</span><span class="n">instance</span><span class="p">()</span>
</span><span class="line"><span class="p">{</span>
</span><span class="line">  <span class="k">if</span> <span class="p">(</span><span class="n">pInstance</span> <span class="o">==</span> <span class="nb">NULL</span><span class="p">)</span> <span class="p">{</span>
</span><span class="line">    <span class="n">pInstance</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Singleton</span><span class="p">();</span>
</span><span class="line">  <span class="p">}</span>
</span><span class="line">  <span class="k">return</span> <span class="n">pInstance</span><span class="p">;</span>
</span><span class="line"><span class="p">}</span>
</span></code></pre></td></tr></table></div></figure></notextile></div>

</div>
  
  
    <footer>
      <a rel="full-article" href="/blog/2016/12/25/singleton/">阅读更多 →</a>
    </footer>
  


    </article>
  
  
    <article>
      
  <header>
    
      <h1 class="entry-title"><a href="/blog/2016/12/04/introductiontohazardpointer/">Lock Free中的Hazard Pointer(下)</a></h1>
    
    
      <p class="meta">
        




<time class='entry-date' datetime='2016-12-04T17:29:10+08:00'><span class='date'><span class='date-month'>Dec</span> <span class='date-day'>4</span><span class='date-suffix'>th</span>, <span class='date-year'>2016</span></span> <span class='time'>5:29 pm</span></time>
        
      </p>
    
  </header>


  <div class="entry-content"><p>在前面几篇<a href="http://www.yebangyu.org/blog/2015/12/10/introduction-to-hazard-pointer/">文章</a>里，我们介绍了Hazard Pointer，一种用于lock free data structure设计中内存管理的利器，这个利器不仅思想简单，还可以用来防止ABA问题，读者诸君务必掌握。</p>

<p>本文作为第三部分，给出工业级代码中，实现Hazard Pointer的一些策略和需要注意的点。</p>

<h2 id="hazard-pointer">Hazard Pointer管理</h2>

<p>我们知道Hazard Pointer封装了原始指针，那么Hazard Pointer的内存和生命周期本身如何管理呢？以下是常见的策略：</p>

</div>
  
  
    <footer>
      <a rel="full-article" href="/blog/2016/12/04/introductiontohazardpointer/">阅读更多 →</a>
    </footer>
  


    </article>
  
  
    <article>
      
  <header>
    
      <h1 class="entry-title"><a href="/blog/2016/12/03/gccandperfopt/">性能优化的那些传说和迷思</a></h1>
    
    
      <p class="meta">
        




<time class='entry-date' datetime='2016-12-03T17:04:10+08:00'><span class='date'><span class='date-month'>Dec</span> <span class='date-day'>3</span><span class='date-suffix'>rd</span>, <span class='date-year'>2016</span></span> <span class='time'>5:04 pm</span></time>
        
      </p>
    
  </header>


  <div class="entry-content"><p>相信你在很多书籍中见到很多代码调优（tuning code）的建议和方法。这些书籍可能包括《编程珠玑》、《深入理解计算机系统》、《程序设计实践》、《Optimized C++》等等。坦白说，这些书我都看过，它们确实提供了不少有意思的性能调优的方法，那么我们的问题是，这些建议和方法有效吗？所谓有效，一种衡量途径是，假如我们不那么做，是否编译器已经会自动优化了呢？</p>

<p>本文我们举几个例子，然后开启编译器优化选项后，看看发生了什么。</p>

<p>本文环境为：Ubuntu 14.04 32bit + Intel I7 CPU + GCC 4.8</p>

<p>生成汇编代码的语句是：<code>g++ -S -O2 code.cpp</code></p>

<h2 id="section">循环展开</h2>

<p>对于下面的函数</p>

<div class="bogus-wrapper"><notextile><figure class="code"><figcaption><span></span></figcaption><div class="highlight"><table><tr><td class="gutter"><pre class="line-numbers"><span class="line-number">1</span>
<span class="line-number">2</span>
<span class="line-number">3</span>
<span class="line-number">4</span>
<span class="line-number">5</span>
<span class="line-number">6</span>
</pre></td><td class="code"><pre><code class="c++"><span class="line"><span class="kt">void</span> <span class="nf">f1</span><span class="p">(</span><span class="kt">int</span> <span class="o">*</span><span class="n">a</span><span class="p">)</span>
</span><span class="line"><span class="p">{</span>
</span><span class="line">  <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="mi">3</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
</span><span class="line">    <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">+</span> <span class="mi">2</span><span class="p">;</span>
</span><span class="line">  <span class="p">}</span>
</span><span class="line"><span class="p">}</span>
</span></code></pre></td></tr></table></div></figure></notextile></div>
<p>它们建议可以将循环展开，变成这样：</p>
<div class="bogus-wrapper"><notextile><figure class="code"><figcaption><span></span></figcaption><div class="highlight"><table><tr><td class="gutter"><pre class="line-numbers"><span class="line-number">1</span>
<span class="line-number">2</span>
<span class="line-number">3</span>
<span class="line-number">4</span>
<span class="line-number">5</span>
<span class="line-number">6</span>
</pre></td><td class="code"><pre><code class="c++"><span class="line"><span class="kt">void</span> <span class="nf">f2</span><span class="p">(</span><span class="kt">int</span> <span class="o">*</span><span class="n">a</span><span class="p">)</span>
</span><span class="line"><span class="p">{</span>
</span><span class="line">  <span class="n">a</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="n">a</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">+</span> <span class="mi">2</span><span class="p">;</span>
</span><span class="line">  <span class="n">a</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">=</span> <span class="n">a</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">+</span> <span class="mi">2</span><span class="p">;</span>
</span><span class="line">  <span class="n">a</span><span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="o">=</span> <span class="n">a</span><span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="o">+</span> <span class="mi">2</span><span class="p">;</span>
</span><span class="line"><span class="p">}</span>
</span></code></pre></td></tr></table></div></figure></notextile></div>

</div>
  
  
    <footer>
      <a rel="full-article" href="/blog/2016/12/03/gccandperfopt/">阅读更多 →</a>
    </footer>
  


    </article>
  
  
    <article>
      
  <header>
    
      <h1 class="entry-title"><a href="/blog/2016/10/13/debuggerforlockfreeprogamming/">一个轻量的lock free程序调试工具</a></h1>
    
    
      <p class="meta">
        




<time class='entry-date' datetime='2016-10-13T22:39:29+08:00'><span class='date'><span class='date-month'>Oct</span> <span class='date-day'>13</span><span class='date-suffix'>th</span>, <span class='date-year'>2016</span></span> <span class='time'>10:39 pm</span></time>
        
      </p>
    
  </header>


  <div class="entry-content"><p>lock free 程序时序混乱，逻辑复杂，反直觉的地方很多，心智负担很重，因此调试起来也非常困难。</p>

<p>下面用C++编写了一个用于调试lock free代码的程序，非常轻量，代码如下，只适用于linux环境。</p>

<div class="bogus-wrapper"><notextile><figure class="code"><figcaption><span></span></figcaption><div class="highlight"><table><tr><td class="gutter"><pre class="line-numbers"><span class="line-number">1</span>
<span class="line-number">2</span>
<span class="line-number">3</span>
<span class="line-number">4</span>
<span class="line-number">5</span>
<span class="line-number">6</span>
<span class="line-number">7</span>
<span class="line-number">8</span>
<span class="line-number">9</span>
<span class="line-number">10</span>
<span class="line-number">11</span>
<span class="line-number">12</span>
<span class="line-number">13</span>
<span class="line-number">14</span>
<span class="line-number">15</span>
<span class="line-number">16</span>
<span class="line-number">17</span>
<span class="line-number">18</span>
<span class="line-number">19</span>
<span class="line-number">20</span>
<span class="line-number">21</span>
<span class="line-number">22</span>
<span class="line-number">23</span>
<span class="line-number">24</span>
<span class="line-number">25</span>
<span class="line-number">26</span>
<span class="line-number">27</span>
<span class="line-number">28</span>
<span class="line-number">29</span>
<span class="line-number">30</span>
<span class="line-number">31</span>
<span class="line-number">32</span>
<span class="line-number">33</span>
<span class="line-number">34</span>
<span class="line-number">35</span>
<span class="line-number">36</span>
<span class="line-number">37</span>
<span class="line-number">38</span>
<span class="line-number">39</span>
</pre></td><td class="code"><pre><code class="c++"><span class="line"><span class="c1">//xx.h</span>
</span><span class="line"><span class="cp">#include &lt;pthread.h&gt;</span>
</span><span class="line"><span class="k">class</span> <span class="nc">LockFreeLogger</span>
</span><span class="line"><span class="p">{</span>
</span><span class="line"><span class="k">public</span><span class="o">:</span>
</span><span class="line">  <span class="k">struct</span> <span class="n">Event</span>
</span><span class="line">  <span class="p">{</span>
</span><span class="line">    <span class="kt">char</span> <span class="o">*</span><span class="n">message</span><span class="p">;</span>
</span><span class="line">    <span class="kt">pthread_t</span> <span class="n">thread_id</span><span class="p">;</span>
</span><span class="line">    <span class="kt">int</span> <span class="n">info</span><span class="p">;</span>
</span><span class="line">  <span class="p">};</span>
</span><span class="line">  <span class="n">LockFreeLogger</span><span class="p">()</span>
</span><span class="line">  <span class="p">{</span>
</span><span class="line">    <span class="n">pos_</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
</span><span class="line">    <span class="n">buffer_</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Event</span><span class="p">[</span><span class="n">SIZE</span><span class="p">];</span>
</span><span class="line">  <span class="p">}</span>
</span><span class="line">  <span class="kt">void</span> <span class="n">log</span><span class="p">(</span><span class="kt">char</span> <span class="o">*</span><span class="n">message</span><span class="p">,</span> <span class="kt">int</span> <span class="n">info</span><span class="p">)</span>
</span><span class="line">  <span class="p">{</span>
</span><span class="line">    <span class="kt">int</span> <span class="n">pos</span> <span class="o">=</span> <span class="n">__sync_fetch_and_add</span><span class="p">(</span><span class="o">&amp;</span><span class="n">pos_</span><span class="p">,</span> <span class="mi">1</span><span class="p">);</span>
</span><span class="line">    <span class="n">buffer_</span><span class="p">[</span><span class="n">pos</span><span class="p">].</span><span class="n">message</span> <span class="o">=</span> <span class="n">message</span><span class="p">;</span>
</span><span class="line">    <span class="n">buffer_</span><span class="p">[</span><span class="n">pos</span><span class="p">].</span><span class="n">info</span> <span class="o">=</span> <span class="n">info</span><span class="p">;</span>
</span><span class="line">    <span class="n">buffer_</span><span class="p">[</span><span class="n">pos</span><span class="p">].</span><span class="n">thread_id</span> <span class="o">=</span> <span class="n">pthread_self</span><span class="p">();</span>
</span><span class="line">  <span class="p">}</span>
</span><span class="line">  <span class="kt">void</span> <span class="n">report</span><span class="p">()</span>
</span><span class="line">  <span class="p">{</span>
</span><span class="line">    <span class="c1">//single thread code</span>
</span><span class="line">    <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">pos_</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
</span><span class="line">      <span class="c1">//cout or fwrite buffer_[i];</span>
</span><span class="line">    <span class="p">}</span>
</span><span class="line">  <span class="p">}</span>
</span><span class="line"><span class="k">private</span><span class="o">:</span>
</span><span class="line">  <span class="kt">int</span> <span class="n">pos_</span><span class="p">;</span>
</span><span class="line">  <span class="n">Event</span> <span class="o">*</span><span class="n">buffer_</span><span class="p">;</span>
</span><span class="line">  <span class="k">static</span> <span class="k">const</span> <span class="kt">int</span> <span class="n">SIZE</span> <span class="o">=</span> <span class="mi">1234567</span><span class="p">;</span>
</span><span class="line"><span class="p">};</span>
</span><span class="line">
</span><span class="line"><span class="k">extern</span> <span class="n">LockFreeLogger</span> <span class="n">logger</span><span class="p">;</span>
</span><span class="line">
</span><span class="line"><span class="cp">#define LOG(message, info) logger.log(message, info)</span>
</span></code></pre></td></tr></table></div></figure></notextile></div>

</div>
  
  
    <footer>
      <a rel="full-article" href="/blog/2016/10/13/debuggerforlockfreeprogamming/">阅读更多 →</a>
    </footer>
  


    </article>
  
  
    <article>
      
  <header>
    
      <h1 class="entry-title"><a href="/blog/2016/09/09/epochbasedreclamation/">Lock Free中的Epoch Based Reclamation</a></h1>
    
    
      <p class="meta">
        




<time class='entry-date' datetime='2016-09-09T22:24:02+08:00'><span class='date'><span class='date-month'>Sep</span> <span class='date-day'>9</span><span class='date-suffix'>th</span>, <span class='date-year'>2016</span></span> <span class='time'>10:24 pm</span></time>
        
      </p>
    
  </header>


  <div class="entry-content"><h2 id="section">楔子</h2>

<p>一般认为，用C/C++编写Lock Free代码非常困难，主要原因无非是两个：</p>

<blockquote>
  <ul>
    <li>内存模型</li>
  </ul>
</blockquote>

<blockquote>
  <ul>
    <li>内存回收</li>
  </ul>
</blockquote>

<p>C++11引入了标准的内存模型，在此之前，C++程序员依赖于具体的体系结构特点和编译器提供的feature来保证正确的内存访问语义。C++11出来后，程序员编写健壮的、可移植的lock free代码成为可能。</p>

<p>但是内存回收问题依旧存在。我们知道，和Java这种提供自动gc的语言相比，C++程序员刀耕火种，得自己管理内存。当一个线程正在访问某块内存，而另外一个线程将它释放将是一个灾难行为。解决内存回收问题在lock free里显得更加困难。</p>

<p>目前用于lock free代码的内存回收的经典方法有：Lock Free Reference Counting、Hazard Pointer、Epoch Based Reclamation、Quiescent State Based Reclamation等。<a href="http://www.yebangyu.org/blog/2015/12/10/introduction-to-hazard-pointer/">上回</a>我们简单介绍了Hazard Pointer，本文我们介绍Epoch Based Reclamation方法。据我所知，这是第一篇介绍这个方法的中文资料。</p>

</div>
  
  
    <footer>
      <a rel="full-article" href="/blog/2016/09/09/epochbasedreclamation/">阅读更多 →</a>
    </footer>
  


    </article>
  
  
    <article>
      
  <header>
    
      <h1 class="entry-title"><a href="/blog/2016/08/21/mcslock/">MCS Lock</a></h1>
    
    
      <p class="meta">
        




<time class='entry-date' datetime='2016-08-21T20:25:11+08:00'><span class='date'><span class='date-month'>Aug</span> <span class='date-day'>21</span><span class='date-suffix'>st</span>, <span class='date-year'>2016</span></span> <span class='time'>8:25 pm</span></time>
        
      </p>
    
  </header>


  <div class="entry-content"><h2 id="section">回顾</h2>

<p><a href="http://www.yebangyu.org/blog/2016/05/26/ticketlock/">上回</a> 我们介绍了Ticket Lock算法，和传统的简单的CAS操作来实现spin lock相比，它提供了不少很好的性质：比如FIFO、没有饥饿等等。</p>

<p>但是根据<a href="https://pdos.csail.mit.edu/papers/linux:lock.pdf">论文</a>，ticket lock的scalability很差。我们不妨简单回顾一下（代码片段也摘自该论文）：</p>

<div class="bogus-wrapper"><notextile><figure class="code"><figcaption><span></span></figcaption><div class="highlight"><table><tr><td class="gutter"><pre class="line-numbers"><span class="line-number">1</span>
<span class="line-number">2</span>
<span class="line-number">3</span>
<span class="line-number">4</span>
<span class="line-number">5</span>
<span class="line-number">6</span>
<span class="line-number">7</span>
<span class="line-number">8</span>
<span class="line-number">9</span>
<span class="line-number">10</span>
<span class="line-number">11</span>
<span class="line-number">12</span>
<span class="line-number">13</span>
<span class="line-number">14</span>
<span class="line-number">15</span>
</pre></td><td class="code"><pre><code class="c++"><span class="line"><span class="k">struct</span> <span class="kt">spinlock_t</span>
</span><span class="line"><span class="p">{</span>
</span><span class="line">  <span class="kt">int</span> <span class="n">current_ticket</span> <span class="p">;</span>
</span><span class="line">  <span class="kt">int</span> <span class="n">next_ticket</span> <span class="p">;</span>
</span><span class="line"><span class="p">}</span>
</span><span class="line"><span class="kt">void</span> <span class="n">spin_lock</span> <span class="p">(</span><span class="kt">spinlock_t</span> <span class="o">*</span><span class="n">lock</span><span class="p">)</span>
</span><span class="line"><span class="p">{</span>
</span><span class="line">  <span class="kt">int</span> <span class="n">t</span> <span class="o">=</span> <span class="n">atomic_fetch_and_inc</span><span class="p">(</span><span class="o">&amp;</span><span class="n">lock</span> <span class="o">-&gt;</span> <span class="n">next_ticket</span> <span class="p">);</span>
</span><span class="line">  <span class="k">while</span> <span class="p">(</span><span class="n">t</span> <span class="o">!=</span> <span class="n">lock</span><span class="o">-&gt;</span><span class="n">current_ticket</span> <span class="p">)</span>
</span><span class="line">  <span class="p">;</span> <span class="cm">/* spin */</span>
</span><span class="line"><span class="p">}</span>
</span><span class="line"><span class="kt">void</span> <span class="n">spin_unlock</span> <span class="p">(</span><span class="kt">spinlock_t</span> <span class="o">*</span><span class="n">lock</span><span class="p">)</span>
</span><span class="line"><span class="p">{</span>
</span><span class="line">  <span class="n">lock</span><span class="o">-&gt;</span><span class="n">current_ticket</span><span class="o">++</span><span class="p">;</span>
</span><span class="line"><span class="p">}</span>
</span></code></pre></td></tr></table></div></figure></notextile></div>

</div>
  
  
    <footer>
      <a rel="full-article" href="/blog/2016/08/21/mcslock/">阅读更多 →</a>
    </footer>
  


    </article>
  
  
    <article>
      
  <header>
    
      <h1 class="entry-title"><a href="/blog/2016/07/12/reentrantlock/">实现可重入锁</a></h1>
    
    
      <p class="meta">
        




<time class='entry-date' datetime='2016-07-12T20:27:25+08:00'><span class='date'><span class='date-month'>Jul</span> <span class='date-day'>12</span><span class='date-suffix'>th</span>, <span class='date-year'>2016</span></span> <span class='time'>8:27 pm</span></time>
        
      </p>
    
  </header>


  <div class="entry-content"><h2 id="section">基本概念</h2>

<p>可重入锁(Reentrant Lock)，是指允许同一个线程多次对该锁进行acquire动作。对于不可重入的锁，当一个线程多次调用acquire后将造成死锁。可重入锁具有广泛的应用，例如：</p>

<div class="bogus-wrapper"><notextile><figure class="code"><figcaption><span></span></figcaption><div class="highlight"><table><tr><td class="gutter"><pre class="line-numbers"><span class="line-number">1</span>
<span class="line-number">2</span>
<span class="line-number">3</span>
<span class="line-number">4</span>
<span class="line-number">5</span>
<span class="line-number">6</span>
<span class="line-number">7</span>
<span class="line-number">8</span>
<span class="line-number">9</span>
<span class="line-number">10</span>
<span class="line-number">11</span>
<span class="line-number">12</span>
<span class="line-number">13</span>
<span class="line-number">14</span>
<span class="line-number">15</span>
<span class="line-number">16</span>
<span class="line-number">17</span>
<span class="line-number">18</span>
<span class="line-number">19</span>
<span class="line-number">20</span>
<span class="line-number">21</span>
<span class="line-number">22</span>
<span class="line-number">23</span>
</pre></td><td class="code"><pre><code class="c++"><span class="line"><span class="k">struct</span> <span class="n">Routine</span>
</span><span class="line"><span class="p">{</span>
</span><span class="line">  <span class="kt">void</span> <span class="n">f</span><span class="p">()</span>
</span><span class="line">  <span class="p">{</span>
</span><span class="line">    <span class="n">lock_</span><span class="p">.</span><span class="n">lock</span><span class="p">();</span>
</span><span class="line">    <span class="n">h</span><span class="p">();</span>
</span><span class="line">    <span class="n">g</span><span class="p">();</span>
</span><span class="line">    <span class="n">lock_</span><span class="p">.</span><span class="n">unlock</span><span class="p">();</span>
</span><span class="line">  <span class="p">}</span>
</span><span class="line">  <span class="kt">void</span> <span class="n">g</span><span class="p">()</span>
</span><span class="line">  <span class="p">{</span>
</span><span class="line">    <span class="n">lock_</span><span class="p">.</span><span class="n">lock</span><span class="p">();</span>
</span><span class="line">    <span class="n">cout</span><span class="o">&lt;&lt;</span><span class="s">&quot;abc&quot;</span><span class="o">&lt;&lt;</span><span class="n">endl</span><span class="p">;</span>
</span><span class="line">    <span class="n">lock_</span><span class="p">.</span><span class="n">unlock</span><span class="p">();</span>
</span><span class="line">  <span class="p">}</span>
</span><span class="line">  <span class="kt">void</span> <span class="n">h</span><span class="p">()</span>
</span><span class="line">  <span class="p">{</span>
</span><span class="line">    <span class="n">lock_</span><span class="p">.</span><span class="n">lock</span><span class="p">();</span>
</span><span class="line">    <span class="n">cout</span><span class="o">&lt;&lt;</span><span class="s">&quot;def&quot;</span><span class="o">&lt;&lt;</span><span class="n">endl</span><span class="p">;</span>
</span><span class="line">    <span class="n">lock_</span><span class="p">.</span><span class="n">unlock</span><span class="p">();</span>
</span><span class="line">  <span class="p">}</span>
</span><span class="line">  <span class="n">Lock</span> <span class="n">lock_</span><span class="p">;</span>
</span><span class="line"><span class="p">};</span>
</span></code></pre></td></tr></table></div></figure></notextile></div>

</div>
  
  
    <footer>
      <a rel="full-article" href="/blog/2016/07/12/reentrantlock/">阅读更多 →</a>
    </footer>
  


    </article>
  
  
    <article>
      
  <header>
    
      <h1 class="entry-title"><a href="/blog/2016/06/26/sequence-lock/">Sequence Lock</a></h1>
    
    
      <p class="meta">
        




<time class='entry-date' datetime='2016-06-26T14:24:59+08:00'><span class='date'><span class='date-month'>Jun</span> <span class='date-day'>26</span><span class='date-suffix'>th</span>, <span class='date-year'>2016</span></span> <span class='time'>2:24 pm</span></time>
        
      </p>
    
  </header>


  <div class="entry-content"><p>在读多写少(Read Mostly)的场景里，我们可能会使用的同步设施包括：</p>

<blockquote>
  <ul>
    <li>Mutex / Spin Lock</li>
    <li>Reader Writer Lock</li>
    <li>Sequence Lock</li>
    <li>Read Copy Update</li>
  </ul>
</blockquote>

<p>前面两种一般人都很清楚了，如雷贯耳、妇孺皆知。如果您对Spin Lock的实现细节有兴趣，建议您阅读我的这几篇博客：</p>

<p><a href="http://www.yebangyu.org/blog/2016/03/04/petersonalgorithm/">Peterson Lock</a></p>

<p><a href="http://www.yebangyu.org/blog/2016/05/26/ticketlock/">Ticket Lock</a></p>

<p><a href="http://www.yebangyu.org/blog/2016/08/21/mcslock/">MCS Queue Lock</a></p>

<p>从今天起，我们介绍后面两种同步设施。今天我们先介绍Sequence Lock。</p>

</div>
  
  
    <footer>
      <a rel="full-article" href="/blog/2016/06/26/sequence-lock/">阅读更多 →</a>
    </footer>
  


    </article>
  
  <div class="pagination">
    
      <a class="prev" href="/posts/2">&larr; Older</a>
    
    <a href="/blog/archives">Blog Archives</a>
    
  </div>
</div>
<aside class="sidebar">
  
    <section>
  <h1>Recent Posts</h1>
  <ul id="recent_posts">
    
      <li class="post">
        <a href="/blog/2017/03/11/2017/">2017技术成长之路</a>
      </li>
    
      <li class="post">
        <a href="/blog/2017/02/17/virtualfunctionandvariadicparametertemplate/">虚函数和变长参数模板的妙用</a>
      </li>
    
      <li class="post">
        <a href="/blog/2016/12/25/singleton/">Singleton与多线程</a>
      </li>
    
      <li class="post">
        <a href="/blog/2016/12/04/introductiontohazardpointer/">Lock Free中的Hazard Pointer(下)</a>
      </li>
    
      <li class="post">
        <a href="/blog/2016/12/03/gccandperfopt/">性能优化的那些传说和迷思</a>
      </li>
    
  </ul>
</section>
<section>
  <h1>Friends' Link</h1>
  <ul>
    <li>
	  <li><a href="http://www.chongh.wiki/">Diting0x</a></li>
	  <li><a href="http://www.xiaolili.net/">wangli</a></li>
	  <li><a href="http://www.skykewei.top">dukewei</a></li>
	  <li><a href="http://irwenqiang.github.io">chenwenqiang</a></li>
      <li><a href="http://www.armsword.com">duruofei</a></li>
    </li>
  </ul>
</section><section>
  <h1>Yebangyu</h1>
  <p>福建人。热爱历史、K歌、NBA</p>
  <p>帝都码农</p>
  <p>历史学家，专治秦汉史</p>
</section>
<section>
 <h1>Categories</h1>
 <ul id="categories">
  <li class='category'><a href='/blog/categories/c-plus-plus/'>c++ (11)</a></li>
<li class='category'><a href='/blog/categories/soupen/'>soupen (4)</a></li>
<li class='category'><a href='/blog/categories/web/'>web (1)</a></li>
<li class='category'><a href='/blog/categories/qi-ta/'>其他 (5)</a></li>
<li class='category'><a href='/blog/categories/li-shi/'>历史 (2)</a></li>
<li class='category'><a href='/blog/categories/bing-xing-bian-cheng/'>并行编程 (20)</a></li>
<li class='category'><a href='/blog/categories/xing-neng-you-hua/'>性能优化 (2)</a></li>
<li class='category'><a href='/blog/categories/suan-fa/'>算法 (4)</a></li>
<li class='category'><a href='/blog/categories/bian-yi-lian-jie/'>编译链接 (2)</a></li>

 </ul>
</section>




  
</aside>

    </div>
  </div>
  <footer role="contentinfo"><!-- mathjax config similar to math.stackexchange -->
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
  jax: ["input/TeX", "output/HTML-CSS"],
  tex2jax: {
    inlineMath: [ ['$', '$'] ],
    displayMath: [ ['$$', '$$']],
    processEscapes: true,
    skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
  },
  messageStyle: "none",
  "HTML-CSS": { preferredFont: "TeX", availableFonts: ["STIX","TeX"] }
});
</script>
<script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML" type="text/javascript"></script>
<p>
  Copyright &copy; 2017 - Yebangyu -
  <span class="credit">Powered by <a href="http://octopress.org">Octopress</a></span>
</p>
<script type="text/javascript">var cnzz_protocol = (("https:" == document.location.protocol) ? " https://" : " http://");document.write(unescape("%3Cspan id='cnzz_stat_icon_1257548193'%3E%3C/span%3E%3Cscript src='" + cnzz_protocol + "s11.cnzz.com/z_stat.php%3Fid%3D1257548193' type='text/javascript'%3E%3C/script%3E"));</script>

</footer>
  











</body>
</html>
